package org.example;


// 双指针：快慢指针和左右指针
public class DoublePointer {

    // 1. 判定链表中是否包含有环
    boolean hasCycle(ListNode head){
        ListNode fast;
        ListNode slow;
        // 初始化快慢指针指向头结点
        fast = head;
        slow = head;
        while(fast != null && fast.next != null){
            // 快指针每次前进两步
            fast = fast.next.next;
            // 慢指针每次前进一步
            slow = slow.next;
            // 如果存在环，快、慢指针必然相遇
            if (fast == slow){
                return true;
            }
        }
        return false;
    }

    // 2. 已知链表中含有环，返回这个环的起始位置
    ListNode detectCycle(ListNode head){
        ListNode fast;
        ListNode slow;
        fast = head;
        slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
        slow = head;
        while(fast != slow){
            // 两个指针以相同的速度前进
            fast = fast.next;
            slow = slow.next;
        }
        // 两个指针相遇的那个单链表节点就是环的起点
        return slow;
    }

    // 3. 寻找无环单链表的中点
    ListNode midpointCycle(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 4. 寻找单链表的倒数第k个元素
    ListNode findKCycle(ListNode head, int k){
        ListNode fast = head;
        ListNode slow = head;
        while(k-- > 0){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    // 左右指针的常用算法
    // 1. 二分搜索(二分搜索nums有序)
    int binarySearch(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target){
                return mid;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else if (nums[mid] > target){
                right = mid - 1;
            }
        }
        return -1;
    }

    // 2. 两数之和
    // 只要数组有序，就应该想到双指针技巧
    // 输入一个已按照升序排列的有序数组nums和一个目标值target，在nums中找到两个数使得它们相加之和等于target，
    // 请返回这两个数的索引（可以假设这两个数一定存在，索引从1开始算）
    int[] twoSum(int[] nums, int target){
        // 左右指针在数组的两端初始化
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int sum = nums[left] + nums[right];
            if (sum == target){
                // 题目要求的索引从1开始的
                return new int[]{left + 1, right + 1};
            }else if (sum < target){
                left++; // 让sum大一点
            }else if (sum > target){
                right--; // 让sum小一点
            }
        }
        return new int[]{-1, -1};
    }

    // 3. 反转数组
    void reverse(int[] nums){
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            // 交换nums[left]和nums[right]
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}
